package test.zj;

import java.util.Arrays;

/**
 * @Description 小于n的最大数字
 * @Author Firenut
 * @Date 2023-08-20 18:17
 */
public class T2_1 {
    // 示例 1：A={1, 2, 9, 4}，n=2533，返回 2499。
    // 示例 2：A={1, 2, 5, 4}，n=2543，返回 2542。
    // 示例 3：A={1, 2, 5, 4}，n=2541，返回 2525。
    // 示例 4：A={1, 2, 9, 4}，n=2111，返回 1999。
    // 示例 5：A={5, 9}，n=5555，返回 999。

    // 对于给定的字符串 2413 和数组[4,6,8],先判断数组能否拼接成与字符串等长的数字
    // 如果能拼接上,说明组装的数字最大值是 2413 - 1 = 2412
    // 如果拼接不上,组装的数字最大位数只能是3,最大值可以取999
    // 然后就是逐个遍历这个最大值的每一位，然后去数组找符合条件的值(因为数组排好序了，所以可以用二分查找)
    // 如果数组中找到的数比当前数要小,那后续之前取数组中最大的元素就行了
    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 5, 4};
        int n = 2541;
        System.out.println(getMaxLessNum(nums, n));
    }

    /**
     * 获取小于N的最大数字
     * @param nums
     * @param n
     * @return
     */
    static String getMaxLessNum(int[] nums, int n) {
        Arrays.sort(nums);
        int maxBelow = getMaxBelow(nums, n);
        String str = String.valueOf(maxBelow);
        StringBuilder sb = new StringBuilder();
        // 用于标识选中的数是否小于str当前位置的元素，
        // 如果是，那么后续都往里追加nums数组的最大值元素即可
        // 否则，需要判断当前位置的数组应该选择哪一个
        boolean flag = false;
        for (int i = 0; i < str.length(); i++) {
            // 循环遍历并进行组装
            char c = str.charAt(i);
            if (flag) {
                sb.append(nums[nums.length - 1]);
            }else{
                int index = getIndex(nums, str, i);
                sb.append(nums[index]);
                if (nums[index] < c - '0') {
                    flag = true;
                }
            }
        }
        return sb.toString();
    }

    /**
     * 查找当前应该要用数组中哪个数字的索引
     * 比如 2411   {2,4,6,8}
     * 能不能选4还得看下一位的1，因为4 后面的 1 比nums中的数值都小，所以组装数字的时候不能选4
     * @param nums
     * @param maxBelow
     * @param i
     * @return
     */
    static int getIndex(int[] nums, String maxBelow, int i) {
        int cur = maxBelow.charAt(i) - '0';
        if (i < maxBelow.length() - 1) {
            int next = maxBelow.charAt(i + 1) - '0';
            if (next < nums[0]) {
                cur -= 1;
            }
        }

        // 查找小于等于cur的下标
        // 1) 先找第一个大于等于cur的索引
        int index = binarySearch(nums, cur);
        // 2) 如果找到的元素比cur大，就往前挪一格
        if (nums[index] != cur) {
            index--;
        }
        return index;
    }


    /**
     * 获取小于n的最大边界值(没法直接确定最大值是多少，只能取边界值)
     * @param nums 数组，存放的是待拼接的数字集合
     * @param n 需要找到一个小于n的最大值
     */
    static int getMaxBelow(int[]nums,int n) {
        // 把n转成字符串,方便后面操作
        String s = String.valueOf(n);
        if (check(s, nums[0])) {
            // 长度可以和n一样
            return n - 1;
        } else {
            // 如果位数小1的话,那就直接都取nums数组中最大的那个元素拼接就行,只要位数-1
            return (int) Math.pow(10, nums.length) - 1;
        }
    }


    /**
     * 检查以minValue开头的数字能否拼接成与str相同长度的字符串
     * 这里入参用String是为了方便逐个数字进行匹配，因为后续可能还有递归调用
     * 如果在方法体里面转成str，会比较麻烦
     * @param str
     * @param minValue
     * @return
     */
    static boolean check(String str, int minValue) {
        char c = str.charAt(0);
        if (minValue < c - '0') {
            return true;
        } else if (minValue == c - '0') {
            // 该位置相同,则递归往下查找
            return check(str.substring(1), minValue);
        }else {
            return false;
        }
    }


    /**
     * 基本的二分查找
     * @param nums
     * @param target
     * @return
     */
    static int binarySearch(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}
